#include <malloc.h>

typedef struct {
	unsigned max_nums;
	unsigned rest_nums;
	unsigned heap_a[];
} SeatManager;

static int get_seat_no(const SeatManager* manager_p, int pos_no) {
	return manager_p->heap_a[pos_no - 1];
}

static void set_seat_no(SeatManager* manager_p, int pos_no, int seat_no) {
	manager_p->heap_a[pos_no - 1] = seat_no;
}

SeatManager* seatManagerCreate(int n) {
	SeatManager* manager_p =
		malloc(sizeof(SeatManager) + sizeof(unsigned[n]));
	manager_p->max_nums = n;
	manager_p->rest_nums = n;
	for (int i = 1; i <= n; i++) {
		set_seat_no(manager_p, i, i);
	}
	return manager_p;
}

int seatManagerReserve(SeatManager* manager_p) {
	int top_seat_no = manager_p->heap_a[0];
	unsigned old_rest_nums = manager_p->rest_nums;
	unsigned seat_no = get_seat_no(manager_p, old_rest_nums);
	unsigned new_rest_nums = old_rest_nums - 1;
	manager_p->rest_nums = new_rest_nums;
	unsigned max_pos_no = new_rest_nums;
	unsigned pos_no = 1;
	while (1) {
		unsigned left_pos_no = (pos_no << 1);
		if (left_pos_no > max_pos_no) {
			break;
		}
		int left_seat_no = get_seat_no(manager_p, left_pos_no);
		int min_child_seat_no = left_seat_no;
		int min_child_seat_pos_no = left_pos_no;
		unsigned right_pos_no = left_pos_no + 1;
		if (right_pos_no <= max_pos_no) {
			int right_seat_no =
				get_seat_no(manager_p, right_pos_no);
			if (right_seat_no < min_child_seat_no) {
				min_child_seat_no = right_seat_no;
				min_child_seat_pos_no = right_pos_no;
			}
		}
		if (seat_no <= min_child_seat_no) {
			break;
		}
		set_seat_no(manager_p, pos_no, min_child_seat_no);
		pos_no = min_child_seat_pos_no;
	}
	set_seat_no(manager_p, pos_no, seat_no);
	return top_seat_no;
}

void seatManagerUnreserve(SeatManager* manager_p, int seat_no) {
	unsigned new_rest_nums = manager_p->rest_nums + 1;
	manager_p->rest_nums = new_rest_nums;
	unsigned pos_no = new_rest_nums;
	while (pos_no > 1) {
		unsigned up_pos_no = (pos_no >> 1);
		int up_seat_no = get_seat_no(manager_p, up_pos_no);
		if (up_seat_no <= seat_no) {
			break;
		}
		set_seat_no(manager_p, pos_no, up_seat_no);
		pos_no = up_pos_no;
	}
	set_seat_no(manager_p, pos_no, seat_no);
}

void seatManagerFree(SeatManager* manager_p) {
	free(manager_p);
}
